The Challenge this month is to write a routine that will accept a list of rectangles and calculate a result based on the intersections of those rectangles. Specifically, your code will return a list of non-overlapping rectangles that contain all points enclosed by an odd (or even) number of the input rectangles. The prototype for the code you should write is:
void RectangleIntersections(
const Rect inputRects[], /* list if input rectangles */
const long numRectsIn, /* number of inputRects */
Rect outputRects[], /* preallocated storage for output */
long *numRectsOut, /* number of outputRects returned */
const Boolean oddParity /* see text for explanation */
);
The parameter oddParity indicates whether you are to return rectangles containing points enclosed by an odd number of the numRectsIn inputRects rectangles (oddParity==true) or by an even (nonzero) number of rectangles (oddParity==false). Sufficient storage for the output will be preallocated for you and pointed to by outputRects.
As an example, if you were given these inputRects:
{0,10,20,30}, {5,15,20,30}
… and oddParity were true, you might return the following list of outputRects:
{0,10,5,15}, {0,15,5,30}, {5,10,15,20}
It would also be correct to return a result that combined the first of these rectangles with either of the other two. If oddParity were false, you would return the following list for the example input:
{5,15,20,30}
The outputRects must be non-empty and non-overlapping. In the example, it would be incorrect to return the following for the odd parity case:
{0,10,5,30} {0,10,20,15}
The outputRects you generate must also be maximal, in the sense that each edge of each of the outputRects should pass through a vertex of one of the inputRects. That is, for example, I don’t want you to return a 1¥1 rectangle representing each point enclosed in the desired number of inputRects. Before returning, set *numRectsOut to indicate the number of outputRects you generated.
If you need auxiliary storage, you may allocate any reasonable amount within your code using toolbox routines or malloc, but you must deallocate that storage before returning. (No memory leaks! – I’ll be calling your code many times.)
This native PowerPC Challenge will be scored using the latest Metrowerks compiler, with the winner determined by execution time. If you have any questions, or would like some test data for your code, please send me e-mail at one of the Programmer’s Challenge addresses, or directly to bob_boonstra@mactech.com. Test data will also be sent to the Programmer’s Challenge mailing list, which you can join by sending a message to autoshare@mactech.com with the SUBJECT line “sub challenge YourName”, substituting your real name for YourName.
